package org.example.day01;

import java.util.*;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO +
 * 给定两个只包含数字的数组a, b, 调整数组a里面数字的顺序，使得尽可能多的a[i] > b[i]。数组a和b中的数字各不相同。 输出所有可以达到最优结果的a数组数量
 * @date 2024/3/11 15:22
 */
public class test006 {

    // 计算所有a的排列中，尽可能多的满足a[i] > b[i]的数量
    public static int countOptimalArrangements(List<Integer> a, List<Integer> b) {
        // 最优结果的数量初始化为0
        int optimalCount = 0;
        // 当前最优结果的最大匹配数初始化
        int maxMatches = 0;

        // 计算a的全排列
        List<List<Integer>> aPermutations = permute(a);

        // 遍历a的全排列
        for (List<Integer> perm : aPermutations) {
            // 计算当前排列下a[i] > b[i]的匹配数量
            int matches = 0;
            for (int i = 0; i < perm.size(); i++) {
                if (perm.get(i) > b.get(i)) {
                    matches++;
                }
            }
            // 如果匹配数量大于当前最优结果的匹配数，则更新最优结果的匹配数，并重置最优结果数量
            if (matches > maxMatches) {
                maxMatches = matches;
                optimalCount = 1;
            }
            // 如果匹配数量等于当前最优结果的匹配数，则最优结果的数量增加1
            else if (matches == maxMatches) {
                optimalCount++;
            }
        }

        return optimalCount;
    }

    // 计算列表的全排列
    public static List<List<Integer>> permute(List<Integer> nums) {
        List<List<Integer>> permutations = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), permutations);
        return permutations;
    }

    // 回溯法计算全排列
    public static void backtrack(List<Integer> nums, List<Integer> permutation, List<List<Integer>> permutations) {
        // 如果当前排列长度等于原列表长度，则将其添加到结果集合中
        if (permutation.size() == nums.size()) {
            permutations.add(new ArrayList<>(permutation));
        } else {
            // 遍历原列表中的每个元素
            for (int i = 0; i < nums.size(); i++) {
                // 如果当前元素已经在排列中，则跳过
                if (permutation.contains(nums.get(i))) {
                    continue;
                }
                // 将当前元素添加到排列中
                permutation.add(nums.get(i));
                // 递归调用下一层
                backtrack(nums, permutation, permutations);
                // 回溯，将当前元素从排列中移除
                permutation.remove(permutation.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        // 输入处理
        Scanner scanner = new Scanner(System.in);
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        String[] aInput = scanner.nextLine().trim().split(" ");
        String[] bInput = scanner.nextLine().trim().split(" ");
        for (String s : aInput) {
            a.add(Integer.parseInt(s));
        }
        for (String s : bInput) {
            b.add(Integer.parseInt(s));
        }

        // 计算最优结果的数量
        int result = countOptimalArrangements(a, b);

        // 输出结果
        System.out.println(result);
    }
}

